package com.wechat.back.utils.ACF;

import java.util.*;

class ACTrie {
    private ACTreeNode root;

    public ACTrie(List<String> words) {
        root = new ACTreeNode();
        for (String word : words) {
            addWord(word);
        }
        initFailover();
    }

    private void initFailover() {
        Queue<ACTreeNode> queue = new LinkedList<>();
        Map<Character, ACTreeNode> children = root.getChildren();
        for (Map.Entry<Character, ACTreeNode> entry : children.entrySet()) {
            ACTreeNode value = entry.getValue();
            value.setFailover(root);
            queue.offer(value);
        }
        while (!queue.isEmpty()) {
            ACTreeNode parentNode = queue.poll();
            for (Map.Entry<Character, ACTreeNode> entry : parentNode.getChildren().entrySet()) {
                ACTreeNode childNode = entry.getValue();
                ACTreeNode failover = parentNode.getFailover();
                while (failover != null &&!failover.hasChild(entry.getKey())) {
                    failover = failover.getFailover();
                }
                if (failover == null) {
                    childNode.setFailover(root);
                } else {
                    childNode.setFailover(failover.childOf(entry.getKey()));
                }
                queue.offer(childNode);
            }
        }
    }

    private void addWord(String word) {
        ACTreeNode wordNode = root;
        char[] words = word.toCharArray();
        for (int i = 0; i < words.length; i++) {
            wordNode.addChildrenIfAbsent(words[i]);
            wordNode = wordNode.childOf(words[i]);
            wordNode.setDepth(i + 1);
        }
        wordNode.setLeaf(true);
    }

    public List<MatchResult> match(String text) {
        List<MatchResult> result = new ArrayList<>();
        ACTreeNode node = root;
        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            while (!node.hasChild(aChar) && node.getFailover() != null) {
                node = node.getFailover();
            }
            if (node.hasChild(aChar)) {
                node = node.childOf(aChar);
                if (node.isLeaf()) {
                    int startIndex = i - node.getDepth() + 1;
                    int endIndex = i + 1;
                    String sensitiveWord = text.substring(startIndex, endIndex);
                    result.add(new MatchResult(startIndex, endIndex, sensitiveWord));
                    node = node.getFailover();
                }
            }
        }
        return result;
    }
}    